package com.algorithm.offer.array;

/**
 * @Author: huangzhigao
 * @Date: 2021/11/28 15:47
 */
public class offer04 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null){
            return false;
        }
        int w = 0;
        int h = matrix[0].length - 1;

        while (w < matrix.length && h > -1) {
            if (matrix[w][h] == target) {
                return true;
            } else if (matrix[w][h] > target) {
                --h;
            } else {
                ++w;
            }
        }
        return false;
    }


    public String replaceSpace(String s) {
        int spaceCount = 0;
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i) == ' '){
                spaceCount++;
            }
        }
        char[] res = new char[s.length()+spaceCount*2];
        int index= res.length-1;
        for(int i = s.length()-1;i>-1;i--){
            if(s.charAt(i) == ' '){
                res[index--] = '0';
                res[index--] = '2';
                res[index--] = '%';
            }else{
                res[index--] = s.charAt(i);
            }
        }
        return String.valueOf(res);
    }

    public int numWays(int n) {
        if(n ==1 || n ==0){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        int p = 0, q =1,sum = 2;
        for(int i = 3;i<=n;i++){
            p = q;
            q = sum;
            sum = (p+q) % 1000000007;
        }
        return sum;
    }

    public int minArray(int[] numbers) {
        for(int i = 0;i<numbers.length-1;i++){
            if(numbers[i]>numbers[i+1]){
                return numbers[i+1];
            }
        }
        return -1;
    }
}
